home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / cuj1008.zip / 1008022A < prev    next >
Text File  |  1992-02-06  |  10KB  |  394 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 2 - QC.CPP: Quadcode support routines
  3. //  by Kenneth Van Camp
  4. ///////////////////////////////////////////////////////
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <assert.h>
  9. #ifdef __TURBOC__
  10. #include <iostream.h>
  11. #else
  12. #include <stream.hpp>
  13. #endif
  14. #include "qc.h"
  15.   
  16. // The following macro returns the number of bytes reqd
  17. // to store a quadcode, given the number of quits:
  18. #define QC_NBYTES(q)    (((q) - 1) / 4 + 1)
  19.  
  20. // These are shifts & masks to extract a single quit
  21. static int  QCshifts[4] = { 6, 4, 2, 0 };
  22. static int  QCmasks[4]  = { 3<<6, 3<<4, 3<<2, 3 };
  23. // This is the inverse mask:
  24. static int  QCimasks[4] =
  25.     { 0xff^(3<<6), 0xff^(3<<4), 0xff^(3<<2), 0xff^3 };
  26. // And these are masks for each bit in a normal byte:
  27. static int  bitmasks[8] =
  28.     { 1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7 };
  29.  
  30. #ifndef STAT_QC
  31. void QuadCode::FreeMem (void)
  32. // Free dynamic memory.
  33. {
  34.   if (nquits > 0 && qca)
  35.     delete qca;
  36.   qca = NULL;
  37.   nquits = 0;
  38. } // QuadCode::FreeMem
  39. #endif // STAT_QC
  40.  
  41. QuadCode::QuadCode (COORD i, COORD j, int nq)
  42. // QuadCode constructor from (I,J) coordinates of the
  43. // upper-left corner of the qc.
  44. // i      is the vertical row# of quadcode (0 at top)
  45. // j      is the horizontal column# of quadcode
  46. // nq     is the # of quits in quadcode
  47. {
  48. #ifndef STAT_QC
  49.   qca = NULL;
  50. #endif
  51.   nquits = 0;
  52.   assert (nq > 0 && nq <= MAXQUITS);
  53.  
  54.   // We traverse both the (i,j) coordinates and the qc
  55.   // from the msb to the lsb and msq to msq.  Note the
  56.   // following assumes MAXQUITS is a multiple of 8.
  57. #ifdef MSB_FIRST
  58.   BYTE *ip = (BYTE *)&i + (MAXQUITS - nq) / 8;
  59.   BYTE *jp = (BYTE *)&j + (MAXQUITS - nq) / 8;
  60. #else
  61.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1 -
  62.       (MAXQUITS - nq) / 8;
  63.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1 -
  64.       (MAXQUITS - nq) / 8;
  65. #endif
  66.  
  67.   int bit = 7 - (MAXQUITS - nq) % 8;
  68.   int nbytes = QC_NBYTES (nq);
  69. #ifndef STAT_QC
  70.   qca = new BYTE [nbytes];
  71.   assert (qca != NULL);
  72. #endif
  73.  
  74.   memset (qca, '\0', nbytes);
  75.   BYTE  *p = qca;
  76.   nquits = nq;
  77.  
  78.   int   pos = 0;        // position within qc (0,1,2,3)
  79.   for ( ; nq > 0; nq--)
  80.   {
  81.     if (*ip & bitmasks[bit])
  82.       *p |= 1 << (QCshifts[pos] + 1);
  83.     if (*jp & bitmasks[bit])
  84.       *p |= 1 << QCshifts[pos];
  85.     // Advance to next quit
  86.     if (++pos > 3)
  87.     {
  88.       pos = 0;
  89.       p++;
  90.     }
  91.     // Back up to next bit
  92.     if (--bit < 0)
  93.     {
  94.       bit = 7;
  95. #ifdef MSB_FIRST
  96.       ip++; jp++;
  97. #else
  98.       ip--; jp--;
  99. #endif
  100.     } // if --bit
  101.  
  102.   } // for nq
  103.  
  104. } // QuadCode::QuadCode
  105.  
  106. void QuadCode::Init (const char *chqc)
  107. // QuadCode initializer from string.
  108. // chqc         is the quadcode in a null-terminated
  109. //              character representation - i.e., "123"
  110. {
  111.   int nq = strlen (chqc);
  112. #ifndef STAT_QC
  113.   qca = NULL;
  114. #endif
  115.   nquits = 0;
  116.   assert (nq > 0 && nq <= MAXQUITS);
  117.   size_t nbytes = QC_NBYTES (nq);
  118. #ifndef STAT_QC
  119.   qca = new BYTE [nbytes];
  120.   assert (qca != NULL);
  121. #endif
  122.   memset (qca, '\0', nbytes);
  123.  
  124.   // Store quadcode in binary form, from msq to lsq.
  125.   int  i;
  126.   int  pos; // pos within byte of this quit (0,1,2,3)
  127.   BYTE *p;  // ptr to current byte in qc
  128.   for (i = 0, pos = 0, p = qca; i < nq; i++)
  129.   {
  130.     int val = chqc[i] - '0';
  131.     assert (val >= 0 && val <= 3);
  132.     *p |= val << QCshifts[pos];
  133.     if (++pos > 3)
  134.     {
  135.       pos = 0;
  136.       p++;
  137.     }
  138.   } // for i
  139.  
  140.   nquits = nq;
  141. } // QuadCode::Init
  142.  
  143. int QuadCode::GetQuit (int quit)
  144. // Return single quit from quadcode.
  145. // quit is the pos# of the quit to extract (zero-based).
  146. //      Pos 0 is the high-order quit ('1' in "123").
  147. {
  148.   assert (quit <= nquits && quit >= 0);
  149.  
  150.   int byte = quit / 4;
  151.   int pos = quit % 4;
  152.   return ( (*(qca + byte) & QCmasks[pos]) >>
  153.       QCshifts[pos]);
  154. } // QuadCode::GetQuit
  155.  
  156. void QuadCode::SetQuit (int quit, int val)
  157. // Set value of a single quit.
  158. // quit is the pos# of the quit to extract (zero-based).
  159. // val  is the value of the quit (0, 1, 2 or 3).
  160. {
  161.   assert (quit <= nquits && quit >= 0 && val >= 0 &&
  162.       val < 4);
  163.  
  164.   BYTE *p = qca + quit / 4;
  165.   int pos = quit % 4;
  166.   // Clear out the old value
  167.   *p &= (255 - QCmasks[pos]);
  168.   // Put in the new value
  169.   *p |= val << QCshifts[pos];
  170. } // QuadCode::SetQuit
  171.  
  172. void QuadCode::ToIJ (COORD &i, COORD &j, int &nq)
  173. // Convert quadcode value to (I,J).
  174. // The offsets returned are the coords of the
  175. // upper-left corner of the quadcode.
  176. // i      is the row#
  177. // j      is the col#
  178. // nq     is the #quits
  179. {
  180.   i = j = nq = 0;
  181.   if (nquits < 1)
  182.     return;
  183.   assert (nquits <= MAXQUITS);
  184.   nq = nquits;
  185.  
  186.   // Go from lsq to msq.  Following loop is based on the
  187.   // conversion algorithm by Gargantini:
  188. #ifdef MSB_FIRST
  189.   BYTE *ip = (BYTE *)&i + sizeof(COORD) - 1;
  190.   BYTE *jp = (BYTE *)&j + sizeof(COORD) - 1;
  191. #else
  192.   BYTE *ip = (BYTE *)&i;
  193.   BYTE *jp = (BYTE *)&j;
  194. #endif
  195.   int   quit,       // current quit# in qc
  196.         bit = 0;    // current bit# in byte of (i,j)
  197.  
  198.   for (quit = nquits-1; quit >= 0; quit--)
  199.   {
  200.     int val = GetQuit (quit);
  201.     // Bit pos 0 gives J val, bit pos 1 gives I val.
  202.     int ival = val >> 1;
  203.     int jval = val & 1;
  204.     *ip |= (ival << bit);
  205.     *jp |= (jval << bit);
  206.     // Advance to next bit
  207.     if (bit == 7)
  208.     {
  209.       bit = 0;
  210. #ifdef MSB_FIRST
  211.       ip--; jp--;
  212. #else
  213.       ip++; jp++;
  214. #endif
  215.     }
  216.     else
  217.       bit++;
  218.   } // for quit
  219.  
  220. } // QuadCode::ToIJ
  221.  
  222. int QuadCode::Compare (QuadCode &qc)
  223. // Compare one quadcode to another.
  224. // Return 0 if the two quadcodes are equal; -1 if the
  225. // current quadcode is less than qc; or +1 if the
  226. // current quadcode is greater than qc.
  227. // qc         is the quadcode to compare to
  228. {
  229.   // Check for zero-length quadcodes
  230.   if (nquits == 0)
  231.   {
  232.     if (qc.nquits == 0)
  233.       return 0;
  234.     else
  235.       return -1;
  236.   }
  237.   else if (qc.nquits == 0)
  238.     return 1;
  239.  
  240.   BYTE *p1 = qca;
  241.   BYTE *p2 = qc.qca;
  242.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  243.   BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
  244.  
  245.   // Compare each byte of the two quadcodes.
  246.   for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
  247.     if (*p1 != *p2)
  248.     {
  249.       if (*p1 < *p2)
  250.         return -1;
  251.       else
  252.         return 1;
  253.     }
  254.  
  255.   if (nquits == qc.nquits)
  256.     // quadcodes same
  257.     return 0;
  258.   else if (nquits < qc.nquits)
  259.     // this quadcode contains qc
  260.     return -1;
  261.   else
  262.     // qc contains this quadcode
  263.     return 1;
  264. } // QuadCode::Compare
  265.  
  266. int QuadCode::Sibling (const QuadCode *qc)
  267. // Compare one quadcode to another.
  268. // Return TRUE if they are siblings, FALSE if not.
  269. // qc         is the quadcode to compare to
  270. {
  271.   // Must be the same length, can't be empty.
  272.   if (qc == NULL || nquits != qc->nquits || nquits==0)
  273.     return (FALSE);
  274.  
  275.   BYTE *p1 = qca;
  276.   BYTE *p2 = qc->qca;
  277.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  278.  
  279.   // Compare each byte of the two quadcodes.
  280.   // If any differ except the last, then not siblings.
  281.   for ( ; p1 < end1; p1++, p2++)
  282.     if (*p1 != *p2)
  283.       return (FALSE);
  284.  
  285.   if (*p1 == *p2)
  286.     // Quadcodes are same
  287.     return (FALSE);
  288.  
  289.   // Make sure final byte matches in all but last quit.
  290.   int pos = (nquits-1) % 4;
  291.   return
  292.       ((*p1 & QCimasks[pos]) == (*p2 & QCimasks[pos]));
  293.  
  294. } // QuadCode::Sibling
  295.  
  296. int QuadCode::Contains (QuadCode &qc)
  297. // Compare one quadcode to another.
  298. // Return TRUE if the current quadcode contains qc
  299. // (i.e., is equal to it or is a parent of it), or
  300. // FALSE otherwise.
  301. // qc         is the quadcode to compare to
  302. {
  303.   if (nquits > qc.nquits)
  304.     return (FALSE);
  305.   if (nquits == 0)
  306.     return (TRUE);
  307.  
  308.   BYTE *p1 = qca;
  309.   BYTE *p2 = qc.qca;
  310.   BYTE *end1 = p1 + QC_NBYTES (nquits) - 1;
  311.   BYTE *end2 = p2 + QC_NBYTES (qc.nquits) - 1;
  312.  
  313.   // Compare each byte of the two quadcodes.
  314.   for ( ; p1 <= end1 && p2 <= end2; p1++, p2++)
  315.     if (*p1 != *p2)
  316.     {
  317.       // Found a byte that differs.  This quadcode
  318.       // contains qc iff: (1) We are at the last byte
  319.       // of this quadcode; and  (2) All quits in this
  320.       // quadcode before the last one match the
  321.       // corresponding quits in qc.
  322.       if (p1 != end1)
  323.         return (FALSE);
  324.       int lastpos = (nquits - 1) % 4;
  325.       int pos;
  326.       for (pos = lastpos; pos >= 0; pos--)
  327.         if ((*p1 & QCmasks[pos]) !=
  328.             (*p2 & QCmasks[pos]))
  329.           return (FALSE);
  330.       // They match up to nquits.
  331.       return (TRUE);
  332.     }
  333.  
  334.   // All bytes match - either qc's are same or this is
  335.   // the parent.
  336.   return (TRUE);
  337. } // QuadCode::Contains
  338.  
  339. void QuadCode::MakeParent (void)
  340. // Make quadcode into its parent.
  341. {
  342.   // Clear the bits that saved the last quit.  Don't
  343.   // bother to reclaim storage if size is reduced.
  344.   nquits--;
  345.   int byte = nquits / 4;
  346.   int pos = nquits % 4;
  347.   *(qca + byte) &= QCimasks[pos];
  348. } // QuadCode::MakeParent
  349.  
  350. QuadCode &QuadCode::operator= (QuadCode &qc)
  351. // Assign one quadcode the same value as another.
  352. // The target quadcode is assumed to be initialized.
  353. // qc         is the quadcode to copy
  354. {
  355. #ifdef STAT_QC
  356.   memcpy (qca, qc.qca, NBYTE_QC);
  357. #else
  358.   FreeMem();
  359.  
  360.   size_t nbytes = QC_NBYTES (qc.nquits);
  361.   qca = new BYTE [nbytes];
  362.   assert (qca != NULL);
  363.   memcpy (qca, qc.qca, nbytes);
  364. #endif  // STAT_QC
  365.  
  366.   nquits = qc.nquits;
  367.   return (*this);
  368. } // QuadCode::operator=
  369.  
  370. ostream &operator<< (ostream &stream, QuadCode &qc)
  371. // Overload "Put to" operator for output to stream.
  372. // stream     is the stream to print to
  373. // qc         is the quadcode to print
  374. {
  375.   int   quit;
  376.  
  377.   for (quit = 0; quit < qc.nquits; quit++)
  378.     stream << (char)(qc.GetQuit (quit) + '0');
  379.   return (stream);
  380. } // operator<<
  381.  
  382. istream &operator>> (istream &stream, QuadCode &qc)
  383. // Overload "Get From" operator for input from stream.
  384. // stream     is the stream to get from
  385. // qc         is the quadcode to store the result in
  386. {
  387.   char  tmp[80];
  388.  
  389.   qc.FreeMem();
  390.   stream >> tmp;
  391.   qc.Init (tmp);
  392.   return (stream);
  393. } // operator>>
  394.